import { create } from "domain";
import { checkArr, random } from "./util";

/**
 * 快速排序
 * @param arr
 */
export const quickSort = (arr: number[]) => {
  const len = arr.length;

  const sort = (start: number, end: number) => {
    // 编辑判断
    if (end - start < 2) return;

    const mid = partition(start, end);

    sort(start, mid);
    sort(mid + 1, end);
  };

  /**
   * 交换两个元素
   * @param {*} l
   * @param {*} r
   */
  const swap = (l: number, r: number) => {
    const tmp = arr[l];
    arr[l] = arr[r];
    arr[r] = tmp;
  };

  const random = (s: number, e: number) => Math.floor(Math.random() * (e - s + 1) + s);

  // 寻找锚点
  const partition = (start: number, end: number) => {
    // 随机选出一个元素和begin交换
    swap(start, random(start, end - 1));

    const pivot = arr[start];

    let s = start,
      e = end - 1;
    while (s < e) {
      // 从后往前找
      while (s < e) {
        if (arr[e] < pivot) {
          // 替换pivot的位置
          arr[s] = arr[e];
          break;
        }
        e--;
      }

      while (s < e) {
        if (arr[s] > pivot) {
          arr[e] = arr[s];
          break;
        }
        s++;
      }
    }

    // start(end)的位置就是pivot最后要插入的位置
    arr[e] = pivot;

    return e;
  };

  sort(0, len);
};
